class Solution
{
public:
    // f[i][j]表示s的前i个数和p的前j个数的匹配情况
    enum
    {
        N = 2010
    };
    bool f[N][N];
    bool isMatch(string s, string p)
    {
        f[0][0] = true;
        for (int i = 0; i < p.size(); ++i)
            if (p[i] == '*')
                f[0][i + 1] = true;
            else
                break;

        for (int i = 1; i <= s.size(); ++i)
            for (int j = 1; j <= p.size(); ++j)
            {
                if (s[i - 1] == p[j - 1])
                    f[i][j] = f[i - 1][j - 1];
                else if (p[j - 1] == '?')
                    f[i][j] = f[i - 1][j - 1];
                else if (p[j - 1] == '*')
                    f[i][j] = f[i - 1][j] || f[i][j - 1];
            }

        return f[s.size()][p.size()];
    }
};